package com.markus.code.有序表;

import java.util.HashMap;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/8 11:26
 * todo: 设计一个LRU缓存
 */
public class LRU {
    /**
     * 封装一个节点
     */
    public static class Node<K,V>{
        K key;
        V val;
        Node<K,V> prev;
        Node<K,V> next;
        public Node(K key,V val){
            this.key = key;
            this.val = val;
        }
    }
    /**
     * 设计一个双端队列
     */
    public static class DequeList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;
        public DequeList(){
            head = null;
            tail = null;
        }

        /**
         * 添加一个头结点
         */
        public void addNode(Node<K,V> node){
            //说明当前链表还没有节点
            if (tail == null){
                head = node;
                tail = head;
            }else{
                tail.next = node;
                node.prev = tail;
                tail = node;
            }
        }

        /**
         * 将节点从头部移到尾部，进行这步操作的原因就是客户端可能使用到了该数据
         */
        public void moveHeadToTail(Node<K,V> node){
            /**
             * node有三种情况，1、已经是尾结点
             *                2、头结点
             *                3、中间节点
             */
            // 1、如果是尾结点，不用进行任何操作
            if (node == tail){
                return;
            }
            // 2、如果是头结点
            if (head == node){
                head = node.next;
                head.prev = null;
            }else{
                //3、最后就是中间节点
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            // 最后就是将该节点移动到尾部
            tail.next = node;
            node.prev = tail;
            node.next = null;
            tail = node;
        }
        public Node<K,V> removeHead(){
            // 说明链表中没有节点
            if (head == null){
                return null;
            }
            Node<K,V> res = head;
            // 只有一个节点
            if (head == tail){
                head = null;
                tail = null;
            }else{
                // 多个节点
                head = res.next;
                head.prev = null;
                res.next = null;
            }
            return res;
        }
    }
    /**
     * 设计一个LRU缓存结构
     */
    public static class MyCache<K,V>{
        private HashMap<K,Node<K,V>> map;
        private DequeList<K,V> dequeList;
        private final int capacity;
        public MyCache(int capacity){
            this.capacity = capacity;
            map = new HashMap<>();
            dequeList = new DequeList<>();
        }
        public void put(K k,V v){
            // 如果原本有这个节点的话，就更新
            if (map.containsKey(k)){
                Node<K,V> node = map.get(k);
                node.val = v;
                dequeList.moveHeadToTail(node);
            }else{
                // 否则就添加
                Node<K,V> node = new Node<>(k,v);
                map.put(k,node);
                dequeList.addNode(node);
                if (map.size() == capacity+1){
                    removeCache();
                }
            }
        }
        public V get(K k){
            // 首先要保证这个节点一定存在
            if (map.containsKey(k)){
                Node<K,V> node = map.get(k);
                dequeList.moveHeadToTail(node);
                return node.val;
            }
            return null;
        }
        private void removeCache(){
            Node<K, V> node = dequeList.removeHead();
            map.remove(node.key);
        }
    }

    public static void main(String[] args) {
        MyCache<Integer,Integer> cache = new MyCache<>(2);
        cache.put(1, 1);
        cache.put(2, 2);
        // 返回  1
        System.out.println(cache.get(1));
        // 该操作会使得关键字 2 作废
        cache.put(3, 3);
        // 返回 -1 (未找到)
        System.out.println(cache.get(2));
        // 该操作会使得关键字 1 作废
        cache.put(4, 4);
        // 返回 -1 (未找到)
        System.out.println(cache.get(1));
        // 返回  3
        System.out.println(cache.get(3));
        // 返回  4
        System.out.println(cache.get(4));
    }
}
